package 动态规划.递归参数思考型;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/24 11:45
 */
public class lc2786访问数组中的位置使分数最大 {
    /*

    [总结：枚举选哪个 vs 选或不选【力扣双周赛 109】_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1AM4y1x7r4/?spm_id_from=333.999.0.0&vd_source=179da737184de5a8f84e4f6c2ee5c350)

     dp 的定义 不一样， 就会导致不同的事件复杂度

     可以 dp[index] 枚举

     也可以dp[index][state] 这样定义
     */


    // f（index， state）  表示 从当前 index  ~ len 在 状态 为 state 时 的最大分数  - 这里的 state 是传递过来的
    // 其实 这里 f（index， state） 这里的 state 表示的 是上一个 元素的 奇偶 情况
    // 那么 递归调用的初始 调用 该 怎么调用呢  正常情况下， 两种都要判断一下 Math，max（f（0， 0），f（0，1））；
    // 但是 该题 的特殊性， 在于 题目 要求 分数的初始值 是nums[0], 表示 nums[0] ,默认是直接 选择的, 所以这里 调用直接 f(0, nums[0] & 1) , 让上一次的state 与 nums[0] 的奇偶相同就可以了
    // 这里的细节 还挺多的
    public long recursion(int index, int state, int x, int nums[],Long[][]dp) {
        if (index == nums.length) {
            return 0;
        }
        if(dp[index][state] != null){
            return dp[index][state];
        }
        long ans = 0;

        if (state == 0) { // even
            // choose

            ans = (nums[index] & 1) == 0 ? recursion(index + 1, 0, x, nums,dp) + nums[index] : recursion(index + 1, 1, x, nums,dp) + nums[index] - x;
            // no choose
//            ans = Math.max(ans, recursion(index, 0, x, nums));

        } else {
            ans = (nums[index] & 1) == 0 ? recursion(index + 1, 0, x, nums,dp) + nums[index] - x : recursion(index + 1, 1, x, nums,dp) + nums[index];
            // no choose
//            ans = Math.max(ans, recursion(index, 0, x, nums));
        }

        // no choose
        dp[index][state] = ans = Math.max(recursion(index + 1, state, x, nums,dp), ans);
        return ans;
    }

    public long solve(int nums[], int x) {
        int state = nums[0] & 1;
       return  recursion(0,state,x,nums,new Long[nums.length + 1][2]);
    }

}



